// 题目描述：
// 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， 
// inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点
// 博文链接：https://blog.csdn.net/ITSOK_123/article/details/123590100
// 题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal


// 递归解决（O(N),O(N)）
class Solution {
    // 前序遍历中树的节点值与下标值的map映射
    unordered_map<int,int> index;
public:
    TreeNode* build(vector<int>& preorder,vector<int>& inorder,int preLow,int preHigh,int inLow,int inHigh){
        // 遍历列表为空返回空树
        if(preLow>preHigh){
            return nullptr;
        }
        // 记录前序遍历中的树的根节点以及中序遍历中的树的根节点
        int preorderRoot = preLow;
        int inorderRoot = index[preorder[preorderRoot]];
        // 构造一颗只有根节点的树
        TreeNode* root = new TreeNode(preorder[preorderRoot]);
        // 确定树的左子树的节点个数
        int leftSize = inorderRoot - inLow;

        root->left = build(preorder,inorder,preLow+1,preLow+leftSize,inLow,inorderRoot-1);

        root->right = build(preorder,inorder,preorderRoot+leftSize+1,preHigh,inorderRoot+1,inHigh);

        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        size_t size = preorder.size();
        // 构建前序遍历中树的节点值与下标值的map映射
        for(int i=0;i<size;i++){
            index[inorder[i]]=i;
        }
        return build(preorder,inorder,0,size-1,0,size-1);
    }
};

// 迭代（O(N),O(N)）
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        size_t n = preorder.size();
        // 空树就返回空指针
        if(n == 0)    return nullptr;
        // 初始化只有根节点的树
        TreeNode* root = new TreeNode(preorder[0]);
        // 初始化保存没有处理过右子节点的节点
        stack<TreeNode*> st;
        // 根节点入栈
        st.push(root);
        // 中序序列遍历下标
        int inorderIndex = 0;
        // 按照前序顺序进行处理
        for(int i=1;i<n;i++){
            // 保存当前节点值
            int preVal = preorder[i];
            // 取出栈顶结点
            TreeNode *node = st.top();
            // 新的节点是栈顶节点孩子
            if(node->val != inorder[inorderIndex]){
                node->left = new TreeNode(preVal);
                st.push(node->left);
            }
            // 新的节点是个右孩子
            else{
                while(!st.empty() && st.top()->val==inorder[inorderIndex]){
                    node = st.top();
                    st.pop();
                    // 中序下标移动
                    ++inorderIndex;
                }
                node->right = new TreeNode(preVal);
                st.push(node->right);
            }
           
        } 
        return root;
    }
};